%% This is file `elsarticle-template-1-num.tex',
%%
%% Copyright 2009 Elsevier Ltd
%%
%% This file is part of the 'Elsarticle Bundle'.
%% ---------------------------------------------
%%
%% It may be distributed under the conditions of the LaTeX Project Public
%% License, either version 1.2 of this license or (at your option) any
%% later version.  The latest version of this license is in
%%    http://www.latex-project.org/lppl.txt
%% and version 1.2 or later is part of all distributions of LaTeX
%% version 1999/12/01 or later.
%%
%% The list of all files belonging to the 'Elsarticle Bundle' is
%% given in the file `manifest.txt'.
%%
%% Template article for Elsevier's document class `elsarticle'
%% with numbered style bibliographic references
%%
%% $Id: elsarticle-template-1-num.tex 149 2009-10-08 05:01:15Z rishi $
%% $URL: http://lenova.river-valley.com/svn/elsbst/trunk/elsarticle-template-1-num.tex $
%%
\documentclass[english,preprint,12pt]{elsarticle}

%% Use the option review to obtain double line spacing
%% \documentclass[preprint,review,12pt]{elsarticle}

%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout:
%% \documentclass[final,1p,times]{elsarticle}
%% \documentclass[final,1p,times,twocolumn]{elsarticle}
%% \documentclass[final,3p,times]{elsarticle}
%% \documentclass[final,3p,times,twocolumn]{elsarticle}
%% \documentclass[final,5p,times]{elsarticle}
%% \documentclass[final,5p,times,twocolumn]{elsarticle}

%% if you use PostScript figures in your article
%% use the graphics package for simple commands
%% \usepackage{graphics}
%% or use the graphicx package for more complicated commands
%% \usepackage{graphicx}
%% or use the epsfig package if you prefer to use the old commands
%% \usepackage{epsfig}

%% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
%% The amsthm package provides extended theorem environments
%% \usepackage{amsthm}

\usepackage{stmaryrd}
\usepackage{color}

%% The lineno packages adds line numbers. Start line numbering with
%% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
%% for the whole article with \linenumbers after \end{frontmatter}.
%% \usepackage{lineno}

%% natbib.sty is loaded by default. However, natbib options can be
%% provided with \biboptions{...} command. Following options are
%% valid:

%%   round  -  round parentheses are used (default)
%%   square -  square brackets are used   [option]
%%   curly  -  curly braces are used      {option}
%%   angle  -  angle brackets are used    <option>
%%   semicolon  -  multiple citations separated by semi-colon
%%   colon  - same as semicolon, an earlier confusion
%%   comma  -  separated by comma
%%   numbers-  selects numerical citations
%%   super  -  numerical citations as superscripts
%%   sort   -  sorts multiple citations according to order in ref. list
%%   sort&compress   -  like sort, but also compresses numerical citations
%%   compress - compresses without sorting
%%
%% \biboptions{comma,round}

% \biboptions{}

\usepackage{listings}
\usepackage{bold-extra}
\usepackage{url}
\usepackage{babel}
\usepackage{array}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{multirow}
\usepackage{comment}

\lstdefinelanguage{ocaml}{
keywords={let, begin, end, in, match, type, and, fun, function, try, with, class, object, method, of, rec, repeat, until,
          while, not, do, done, as, val, inherit, module, sig, deriving, datatype, struct, if, then, else, ostap},
sensitive=true
}

\lstdefinelanguage{oberon0}{
keywords={MODULE, END, PROCEDURE, VAR, TYPE, CONST, FOR, WHILE, CASE, IF, BEGIN, ELSIF, THEN, ARRAY, OF, RECORD, DO},
sensitive=true
}

\newcommand{\oberonsize}{\fontsize{9pt}{9pt}}
\lstnewenvironment{oberon0} {\lstset{language={oberon0}}\oberonsize}{}
\newcommand\textoberon[1]{{\lstinline[language={oberon0}]{#1}}}
\newcommand\textoberonF[1]{{\oberonsize\lstinline[language={oberon0}]{#1}}}

\lstdefinelanguage{scala}{
   keywords={abstract,case,catch,class,def,do,else,extends,false,final,
     finally,for,forSome,if,implicit,import,lazy,match,new,null,
     object,override,package,private,protected,requires,return,
     sealed,super,this,throw,trait,try,true,type,val,var,while,
     with,yield},
   sensitive=true
}

\newcommand{\scalasize}{\fontsize{9pt}{9pt}}
\lstnewenvironment{scala} {\lstset{language={scala}}\scalasize}{}
\newcommand\textscala[1]{{\lstinline[language={scala}]{#1}}}
\newcommand\textscalaF[1]{{\scalasize\lstinline[language={scala}]{#1}}}

\lstset{
basicstyle=\small\ttfamily,
identifierstyle=\ttfamily,
keywordstyle=\ttfamily\bfseries,
commentstyle=\scriptsize\rmfamily,
basewidth={0.5em,0.5em},
fontadjust=true
}

\journal{Science of Computer Programming}

%%%% Rascal needed stuff
\usepackage{xspace,rascal/rascal,float}
%\floatstyle{ruled}
\newfloat{listing}{htbp}{lol}
\floatname{listing}{Listing}
%%%% End Rascal needed stuff

\begin{document}

\begin{frontmatter}

%% Title, authors and addresses

%% use the tnoteref command within \title for footnotes;
%% use the tnotetext command for the associated footnote;
%% use the fnref command within \author or \address for footnotes;
%% use the fntext command for the associated footnote;
%% use the corref command within \author for corresponding author footnotes;
%% use the cortext command for the associated footnote;
%% use the ead command for the email address,
%% and the form \ead[url] for the home page:
%%
%% \title{Title\tnoteref{label1}}
%% \tnotetext[label1]{}
%% \author{Name\corref{cor1}\fnref{label2}}
%% \ead{email address}
%% \ead[url]{home page}
%% \fntext[label2]{}
%% \cortext[cor1]{}
%% \address{Address\fnref{label3}}
%% \fntext[label3]{}

\title{LDTA Tool Challenge}

%% use optional labels to link authors explicitly to addresses:
%% \author[label1,label2]{<author name>}
%% \address[label1]{<address>}
%% \address[label2]{<address>}

\author[tue]{Mark van den Brand}

% Please add your names below, we can sort out the order later.

\author[umn]{Eric Van Wyk}
\author[umn]{Ted Kaminski}

\author[lu]{Niklas Fors}
\author[lu]{G{\"o}rel Hedin}
\author[cwi]{Tijs van der Storm}

\author[mq]{Anthony M. Sloane}

\author[cy]{Margus Freudenthal}

\author[spbu]{Dmitry Boulytchev}

\author[uu]{Doaitse Swierstra}

\author[udelar]{Marcos Viera}


\address[tue]{Technical University of Eindhoven, Eindhoven, The Netherlands}
\address[umn]{University of Minnesota, Minneapolis, MN, United States}
\address[lu]{Lund University, Lund, Sweden}
\address[mq]{Macquarie University, Sydney, Australia}
\address[cy]{Cybernetica AS / University of Tartu, Tartu, Estonia}
\address[spbu]{St-Petersburg State University, St.Petersburg, Russia}
\address[cwi]{Centrum Wiskunde \&\ Informatica, Amsterdam, The Netherlands}
\address[uu]{Utrecht University, Utrecht, The Netherlands}
\address[udelar]{University of the Republic, Montevideo, Uruguay}

\begin{abstract}

An abstract goes here...

\end{abstract}

\begin{keyword}
%% keywords here, in the form: keyword \sep keyword

%% MSC codes here, in the form: \MSC code \sep code
%% or \MSC[2008] code \sep code (2000 is the default)

\end{keyword}

\end{frontmatter}

%%
%% Start line numbering here if you want
%%
% \linenumbers

%% main text
\section{Introduction}
\label{sec:intro}

Computer science reached its maturity thanks to, among others, the research on compilation techniques
and development of compilers for the broad range of programming languages. 
Since the early days of compiler construction researchers have been exploring tools and techniques to 
describe languages and generate parts of the compiler from these descriptions. 
The most well-known tools in the field are LEX+YACC (including
all variations) \cite{Lesk1990, Joh75.yacc}, attribute grammars systems, and programming environment
generators, for instance the Synthesizer Generator \cite{Reps1989}. This list is non-exhaustive and
certainly too short, but gives an impression of the early stage development of compiler generator related tools. 

Most compiler oriented conferences focussed on the construction of compilers, parsing and code optimization.
The research area of how to describe a programming language so that efficient tooling can be generated from
this description was more or less neglected, although that quite a number of formalisms and tools were developed
over the years.
Early 2000 the workshop series on Language Descriptions, Tools and Applications (LDTA) \footnote{www.ldta.info} 
at ETAPS \footnote{www.etaps.org} was started. 
The focus of this workshop series was on the description of (programming) languages and
the development and/or generation of tools for these languages, and the applications of these formalisms
and tools. 
This workshop series was active until 2012 and it was terminated because of the starting of the
Software Language Engineering conference in 2008. Since the start of LDTA in 2000 a returning theme
was the comparison of tools developed for describing (programming) languages and generation of
parts of a compiler. In 2011 the tool challenge was organized. This tool challenge
``was a community-building exercise to get tool developers working on the same problem, but with 
different tools and techniques. The goal was to create a discussion that fosters a better understanding, 
among tool developers and tool users, of relative strengths and weaknesses of different language 
processing tools, techniques, and formalisms.''.\footnote{www.ldta.info/2011/tool.html}

This paper is describes the tool challenge in detail. The paper does not address a specific scientific
aspect on language description or tool usage. So, one can ask the questions; why a tool challenge
and why to write such a lengthy paper about this tool challenge? The goal was to see how the various
tools would be able to deal with the tasks set by the challenge. The outcome is not only a comparison of 
the tools involved, but also a reflection on why are these tools not yet mainstream technology in the area
of compiler construction. An observation is that the systems involved play an (important) role when
describing domain specific languages. They offer a short turn-around time with respect to rapid prototyping
of languages.
However, the challenge shows that the tools are powerful enough to implement a full compiler on a 
high level of abstraction. 

The first step in establishing the tool challenge
was the selection of the programming language that had to be specified. It is obvious that a full blown
language like Java was out of scope. The language had to be non-trivial but not too complex. Furthermore,
a decent description of the language should be available with a precise definition of the syntax and
more important a non-ambigous definition of the semantics. Having a reference compiler would make the
language complete. The Oberon language \cite{Wirth96} developed by Wirth turn out to fulfill all the
requirements formulated above. The Oberon language is presented in Section \ref{sec:oberon}.

The challenge was split into five tasks. The tasks are traditional compiler tasks when implementing a compiler
for an imperative programming language.
\begin{description}
\item[T1] \emph{Parsing and pretty printing.} The goal is to build a tool that reads in the programs, constructs
the corresponding parse tree, and then pretty-prints the parse tree. 
\item[T2] \emph{Name binding.} The goal of this task is to build a tool that reads in syntactically valid programs
and binds all name uses to their declarations. If a name is not declared or declared more than once an error
message should be generated.
\item[T3] \emph{Type checking.} The goal of this task is to check that the program does not contain
type errors. If a type error is found, an appropriate error message should be generatoed. 
The implemented solutions should provide informative and helpful error message at an
appropriate abstraction level.

\item[T4] \emph{Source-to-source transformations.}
There are two source-to-source transformation tasks.
\begin{description}
\item[T4a] The first task focusses on the translation of language features introduced
in extended versions of the languages to language constructs in a basic (implemented)
version of the language. For instance, control flow constructs introduced in the extended
version, L2 (see Section \ref{ref:oberon}), should be translated to the core language. L1.
\item[T4b] The second taks focusses on more traditional optimizations. One can think of
constant propagation, dead code elimination, common sub-expression elimination, and
strength reduction.
\end{description}
\item[T5] \emph{Code generation.}
There are also two code generation tasks.

\begin{description}
\item[T5a] The first task consists of translating the Oberon language to ANSI-C. This code generation step is rather
straightforward because of Oberon and C share many language constructs.
\item[T5b] The second task consists of translating Oberon to a lower-level language: Wirth's DLX, a simple RISC assembly
language. The optimizations of Task T4b may also be applied on the generated DLX code.
\end{description}
\end{description}

The challenge had an open call for participation and the first results where presented at the LDTA workshop
in 2011. 
Although that more systems where presented at the workshop, seven systems contributed to this paper.
Each of the systems is a separate section in the paper, where the sections describe the characteristics
of the system and the findings when writing the specifications.

\begin{itemize}
\item How to read the paper?
\item Systems involved
\item Handling of artifacts
\end{itemize}

\input{oberon0}

% 3--8 Systems
% Please add an input line below for your paper section.  We can sort
% out the order of these later.

%%\input{silver/silver}
%%\input{jastadd/jastadd}
%%\input{rascal/rascal}
%%\input{ocaml/ocaml}
%%\input{kiama/kiama}
%%\input{simpl/simpl}
%%\input{cococo/cococo}

\section{Comparison of implementations}
\label{sec:comparison}
\begin{itemize}
\item Quantitative comparison (LoC)
\item Qualitative comparison
\end{itemize}

\section{Observations}
\label{sec:observations}

\section{Conclusions}
\label{sec:conclusions}



\appendix

\section{Oberon 0 code}
\label{sec:samples}
Appendix contains example of Oberon code with line numbers


%% The Appendices part is started with the command \appendix;
%% appendix sections are then done as normal sections
%% \appendix

%% \section{}
%% \label{}

%% References
%%
%% Following citation commands can be used in the body text:
%% Usage of \cite is as follows:
%%   \cite{key}          ==>>  [#]
%%   \cite[chap. 2]{key} ==>>  [#, chap. 2]
%%   \citet{key}         ==>>  Author [#]

%% References with bibTeX database:

%\bibliographystyle{model1-num-names}
\bibliographystyle{elsarticle-num}
\bibliography{main,silver/silver,jastadd/jastadd,ocaml/ocaml,kiama/kiama,simpl/simpl,cococo/cococo,rascal/rascal}

%% Authors are advised to submit their bibtex database files. They are
%% requested to list a bibtex style file in the manuscript if they do
%% not want to use model1-num-names.bst.

%% References without bibTeX database:

% \begin{thebibliography}{00}

%% \bibitem must have the following form:
%%   \bibitem{key}...
%%

% \bibitem{}

% \end{thebibliography}


\end{document}

%%
%% End of file `elsarticle-template-1-num.tex'.
